
// 数组实现队列：
// 法一：空出一个空间，用于区分队列空和队列满,使用front表示队首元素，rear表示队尾的下一个下标，即左闭右开[head,tail)
class CircularQueueFunc1 {
    private int[] items = new int[100];
    private int front = 0;
    private int rear = 0;

    public CircularQueueFunc1() {}

    public void put(int val){
        // 这里还需要%数组长度的原因是：插入第99(下标为98)个元素后，rear为99加一取模才能回到0去和front比较
        //       可以发现其它时候，其实都可以省略if取模，直接就是if((rear+1) == front)。
        //       当然，如果也已经出队了一些元素，那就不满足队满的条件，那就继续放元素，然后下面rear+1就变成100
        //       然后rear就取模归位到0，达到循环的目的。
        // 比如已经连续插入98(下标0-97)个数,要插入第99(下标98)个数时，rear=98，还不满足队列满的条件
        // 继续往下,rear+1之后，rear变成了99，rear取余数还是99。
        // 当要插入第100个数时：此时rear=99，表示队尾的下一个的下标，即队列已经有99个数(下标0-98)
        // 此时判断if,rear+1就是100，取模后就是0，发现满足队列满，直接返回
        if((rear+1) % items.length == front){
            // 队列满，
            return;
        }
        items[rear] = val;
        rear++;
        rear = rear % items.length;
    }
    public Integer take(){
        if(rear == front){
            return null;
        }
        int result = items[front];
        front++;
        front = front % items.length;  // 出队元素归位

        return result;
    }
}

// 法二：使用size记录队列元素个数,此时数组全部空间都可放元素。使用head表示队首元素，tail表示队尾的下一个下标，依然是[head,tail)
class CircularQueueFunc2 {
    private int[] items = new int[100];
    private int head = 0;
    private int tail = 0;
    private int size = 0;

    public void put(int val){
        if(size == items.length){
            return;
        }
        items[tail] = val;
        tail++;
        size++;
        // tail = tail % items.length;
        if(tail == items.length){       // 上面的取模操作和这一步操作功能一样，但是这里的比较比取模效率高，且代码可读性更高。
            tail = 0;
        }
    }
    public Integer take(){
        if(size == 0){
            return null;
        }
        int result = items[head];
        head++;
        size--;
        if (head == items.length){
            head = 0;
        }

        return result;
    }
}

public class Main {
    public static void main(String[] args) {
        CircularQueueFunc1 f1 = new CircularQueueFunc1();
        f1.put(1);
        f1.put(2);
        f1.put(3);
        f1.put(4);

        System.out.println(f1.take());
        System.out.println(f1.take());
        System.out.println(f1.take());
        System.out.println(f1.take());
    }
}
